#include <cstdlib>
#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;
#define M 1024
int x[M] = {0}; // 最优解
int dp[M][M];   // 最优值
int m[M][M];

// 转化为0-1背包问题
//           效益度     约束     最优值   最优解
// 0-1背包    价值v      重量w      m        x
// 购物     渴望程度v    价格p      dp       X

// 自底向上计算最优值
void Knapsack(int *v, int *w, int c, int n, int m[][M])
{
    int jMax, j, i;
    jMax = (w[n] - 1) < c ? (w[n] - 1) : c;
    for (j = 0; j <= jMax; j++)
        m[n][j] = 0;
    for (j = w[n]; j <= c; j++)
        m[n][j] = v[n];
    // 这部分是计算m[n][j]的值。
    for (i = n - 1; i > 1; i--)
    {
        jMax = (w[i] - 1) < c ? (w[i] - 1) : c;
        for (j = 0; j <= jMax; j++)
            m[i][j] = m[i + 1][j];
        for (j = w[i]; j <= c; j++)
            m[i][j] = m[i + 1][j] > (m[i + 1][j - w[i]] + v[i]) ? m[i + 1][j] : (m[i + 1][j - w[i]] + v[i]);
    }
    m[1][c] = m[2][c];
    if (c >= w[1])
        m[1][c] = m[1][c] > (m[2][c - w[1]] + v[1]) ? m[1][c] : (m[2][c - w[1]] + v[1]);
}

void Traceback(int m[][M], int *w, int c, int n, int *x)
{
    int i;
    for (i = 1; i < n; i++)
        if (m[i][c] == m[i + 1][c])
            x[i] = 0;
        else
        {
            x[i] = 1;
            c = c - w[i];
        }
    x[n] = (m[n][c]) ? 1 : 0;
}

int main()
{
    int n, w[10], v[10], c, i;
    n = 5;//物品数量
    c = 10;//背包容量
    w[1] = 2;
    w[2] = 2;
    w[3] = 6;
    w[4] = 5;
    w[5] = 4;
    v[1] = 6;
    v[2] = 3;
    v[3] = 5;
    v[4] = 4;
    v[5] = 6;
    Knapsack(v, w, c, n, m);
    Traceback(m, w, c, n, x);
    printf("m[1][c]=%d", m[1][c]);
    for (i = 1; i <= n; i++)
        printf("\nnumber%d bag is %s", i, x[i] ? "in" : "out");

    return 0;
}

/*
5 10
2 6
2 3
6 5
5 4
4 6
*/